Still color graphics images are widely used for display by computer systems, especially by multimedia personal computers (PCs). As the degree of resolutions provided and the number of colors capable of being represented in an image get higher, the size of the data representing the color graphics image grows larger. Also, as bigger computer monitors are used, users require the display of larger images. Reduction of the memory space needed to store color graphics images and reduction of the time needed to transmit and display such images has been, and continues to be, an important goal in computer graphics technology.
FIG. 1 is a prior art diagram of a color graphics image and its associated storage representation. A bitmap image 10 has n lines of m pixels per line. Typically, both n and m are divisible by eight. Hence, the bitmap image 10 can be logically divided up into square blocks of 8 pixels by 8 pixels. Thus, there are m/8 blocks across the horizontal axis of the bitmap image, and n/8 blocks down the vertical axis of the bitmap image, or (m/8 * n/8) 8.times.8 blocks in the bitmap image. A given 8.times.8 block can be referenced by a (i, j) pair, where i is in the range 0 to (m/8-1), and j is in the range 0 to (n/8-1).
Each 8.times.8 block 12 therefore contains 64 pixels. Each pixel is represented as a RGBA quadruplet 14. The RGBA quadruplet 14 includes a red color value (R) 16, a green color value (G) 18, a blue color value (B) 20, and a brightness value (A) 22. The color and brightness of the pixel are determined by the R, G, B, and A values. For most color images, an 8.times.8 block contains 5 to 12 different colors. Each of the R, G, B, and A values is stored in an eight-bit byte. Therefore, each pixel occupies 4 bytes of storage, and an 8.times.8 block occupies 256 bytes of storage. Accordingly, the bitmap image 10 requires 256 * (m/8 * n/8) bytes of storage. For example, if the bitmap image is 640 pixels per line by 480 lines, the size of uncompressed bitmap image data is 256 * (640/8 * 480/8), which is 1,228,800 bytes. For a bitmap image of 1280 pixels per line by 1024 lines, the size of the uncompressed bitmap image is 256 * (1280/8 * 1024/8), which is 5,242,880 bytes. Hence, uncompressed bitmap images require large amounts of storage.
One method of still image compression was devised by the Joint Photographic Experts Group (JPEG), a group sanctioned by the International Standards Organization (ISO). The JPEG compression standard is a lossy image compression algorithm that reduces the size of bitmapped images with little discernable image degradation. Lossy compression methods reduce the size of the image by disregarding some pictorial information. In contrast, lossless compression methods reduce the number of bits an image would normally require without losing any data. The JPEG compression algorithm converts a color image into rows of pixels, each pixel having numerical values representing brightness and color as described above. The image is broken down into blocks, each block being 16 pixels by 16 pixels, and then reduced to blocks of 8 pixels by 8 pixels by subtracting every other pixel in each block. The compression algorithm uses a formula that computes an average color value for each block, permitting it to be represented with less data. To retrieve the image data, the process is simply reversed to decompress the image.
Although widely used, the JPEG standard has disadvantages. The JPEG algorithm uses Fourier transformation, Hoffman coding, "zigzagging", and YUV transformation calculations to compute local average color values for related pixels in the image. The algorithm represents each color used in a row of pixels in the image as a curve. The local average color values are computed by calculating cosine functions and by multiplying floating point coefficients for terms of the polynomial equation representing the curve. These computations are relatively slow, negatively affecting the overall image compression and decompression speed. A faster method of compressing and decompressing color graphics images is needed which does not require floating point computation of cosine functions and multiplication operations. Furthermore, a method which provides a good compression ratio and allows for a high degree of parallelism during decompression would be a valuable addition to the computer graphics art.